package com.yt.ds.chapter3;

/**
 * @Author: lzf
 * @Date: 2020/7/22 15:01
 * @Description: 红黑树
 */
public class RedBlackBST<Key extends Comparable<Key>, Value> implements ST<Key, Value> {
    private Node root;

    private static final boolean RED = true;
    private static final boolean BLACK = false;

    private class Node {
        Node right;
        Node left;
        Key key;
        Value val;
        int n;      // 结点数 包括根节点
        boolean color;  // 从父结点指向该结点的颜色

        public Node(Key key, Value val, int n, boolean color) {
            this.key = key;
            this.val = val;
            this.n = n;
            this.color = color;
        }
    }

    /**
     * 是否是红色链接
     */
    private boolean isRed(Node node) {
        if (node == null) {
            return BLACK;
        }
        return node.color == RED;
    }

    /**
     * 描述：目标结点左旋
     *
     * @param h 目标结点
     * @return "com.yt.ds.chapter3.RedBlackBST<Key,Value>.Node"
     * @date: 2020/7/22 17:02
     */
    private Node rotateLeft(Node h) {
        Node x = h.left;
        h.left = x.right;
        x.right = h;
        x.color = h.color;
        h.color = RED;
        x.n = h.n;
        h.n = size(h.right) + size(h.left) + 1;
        return x;
    }

    /**
     * 描述：目标结点右旋转
     *
     * @param h 目标结点
     * @return "com.yt.ds.chapter3.RedBlackBST<Key,Value>.Node"
     * @date: 2020/7/22 17:16
     */
    private Node rotateRight(Node h) {
        Node x = h.left;
        h.left = x.right;
        x.right = h;
        x.color = h.color;
        h.color = RED;
        x.n = h.n;
        h.n = size(h.right) + size(h.left) + 1;
        return x;
    }

    /**
     * 描述：颜色转换[目标结点左右子树变为黑色，父结点变为红色]
     *
     * @param h 目标结点
     * @return "void"
     * @date: 2020/7/24 15:26
     */
    private void flipColors(Node h) {
        h.color = RED;
        h.left.color = BLACK;
        h.right.color = BLACK;
    }

    /**
     * 描述：插入算法
     *
     * @param key   键
     * @param value 值
     * @return "void"
     * @date: 2020/7/24 15:54
     */
    @Override
    public void put(Key key, Value value) {
        root = put(root, key, value);
        root.color = BLACK;
    }

    private Node put(Node node, Key key, Value value) {
        if (node == null) {
            return new Node(key, value, 1, RED);
        }

        int com = key.compareTo(node.key);
        if (com < 0) {
            node.left = put(node.left, key, value);
        } else if (com > 0) {
            node.right = put(node.right, key, value);
        } else {
            node.val = value;
        }

        if (isRed(node.right) && !isRed(node.left)) {
            node = rotateLeft(node);
        }
        if (isRed(node.left) && isRed(node.left.left)) {
            node = rotateRight(node);
        }
        if (isRed(node.left) && isRed(node.right)) {
            flipColors(node);
        }

        node.n = size(node.left) + size(node.right) + 1;
        return node;
    }

    @Override
    public Value get(Key key) {
        return null;
    }

    // TODO: 2020/7/24 删除操作待定
    @Override
    public void delete(Key key) {

    }

    @Override
    public void deleteMin() {

    }

    @Override
    public int size() {
        return size(root);
    }

    /**
     * 获取大小
     */
    public int size(Node node) {
        return node == null ? 0 : node.n;
    }

    @Override
    public boolean isEmpty() {
        return false;
    }

    @Override
    public Key min() {
        return null;
    }

    @Override
    public Key max() {
        return null;
    }

    @Override
    public Key floor(Key key) {
        return null;
    }

    @Override
    public int rank(Key key) {
        return 0;
    }

    @Override
    public Key select(int n) {
        return null;
    }

    @Override
    public void display() {

    }
}
